package ai;

import boardgame.*;
import java.util.*;

public class Minimax {
	
	public final Move searchBestMove(final GameState g, int searchDepth)
	{
		Vector<Move> moveList = g.generateMoves();
		
		if (moveList.isEmpty())
			return null;
		
		
		Iterator<Move> moveIterator = moveList.iterator();
		
		Move bestMove = moveIterator.next();
		int bestScore = alphaBetaMin(g.simulateMove(bestMove), searchDepth, Integer.MIN_VALUE+1,Integer.MAX_VALUE);
		
		int evalScore;
		Move evalMove;
		while (moveIterator.hasNext())
		{
			evalMove = moveIterator.next();
			evalScore = alphaBetaMin(g.simulateMove(evalMove), searchDepth, Integer.MIN_VALUE+1, Integer.MAX_VALUE);
			if (evalScore > bestScore){
				bestScore = evalScore;
				bestMove = evalMove;
			}
		}
		return bestMove;
	}
	
	public final int alphaBetaMax(final GameState g, int depth, int alpha, int beta)
	{
		Vector<Move> moveList = g.generateMoves();
		
		if (moveList.isEmpty() || depth <= 0)
			return g.evaluate();
		
		Iterator<Move> moveIterator = moveList.iterator();
		while(moveIterator.hasNext()){
			alpha = Math.max(alpha,alphaBetaMin(g.simulateMove(moveIterator.next()),depth-1,alpha,beta));
			if (beta <= alpha)
				break;	//alpha-beta cut-off
		}
		return alpha;		
	}
	
	public final int alphaBetaMin(final GameState g, int depth, int alpha, int beta)
	{
		Vector<Move> moveList = g.generateMoves();
		
		if (moveList.isEmpty() || depth <= 0)
			return g.evaluate();
		
		Iterator<Move> moveIterator = moveList.iterator();
		while(moveIterator.hasNext()){
			beta = Math.min(beta,alphaBetaMax(g.simulateMove(moveIterator.next()),depth-1,alpha,beta));
			if (beta <= alpha)
				break;	//alpha-beta cut-off
		}
		return beta;		
	}
}
